<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
  <title>C++ Tutorial: Binary Tree</title>
  <meta
 content="C++ Tutorial: Binary Tree, Source Code"
 name="description" />
  <meta
 content="C++ Tutorial, Binary Tree"
 name="keywords" />
  <meta http-equiv="Content-Type"
 content="text/html; charset=ISO-8859-1" />
  <link type="text/css" rel="stylesheet" href="../images/bogostyleWidePre.css" />
</head>
<body>
<div id="page" align="center">
<div id="content" style="width: 800px;">
<div id="logo">
<div class="whitetitle" style="margin-top: 70px;">bogotobogo </div>
</div>
<div id="topheader">
<div class="headerbodytext" align="left"><br />
<strong>Bogotobogo</strong><br />
contact@bogotobogo.com </div>
<div class="smallgraytext" id="toplinks"><a href="../index.html">Home</a>
| <a href="../sitemap.html">Sitemap</a>
| <a href="../blog" target="_blank">Contact Us</a>
</div>
</div>
<div id="menu">
<div class="smallwhitetext" style="padding: 9px;" align="right"><a
 href="../index.html">Home</a>
| <a href="../about_us.html">About Us</a>
| <a href="../products.html">Products</a>
| <a href="../our_services.html">Our Services</a>
| <a href="../blog" target="_blank">Contact Us</a>
</div>
</div>
<div id="submenu">
<div class="smallgraytext" style="padding: 9px;" align="right"><a
 href="../gif.html">Gif</a> |
<a href="../java_applet.html">JavaApplet/Web Start</a>
| <a href="../flash.html">Flash</a>
| <a href="../shockwave.html">ShockWave</a>
| <a href="../svg.html">SVG</a>
| <a href="../iPhone.html">iPhone/iPad</a>
| <a href="../android.html">Android</a>
| <a href="../OnHTML5.html">HTML5</a>
| <a href="../Algorithms/algorithms.html">Algorithms</a>
| <a href="../News/NewsMain.html">News</a>
| <a href="../cplusplus/cpptut.html">C++</a>
| <a href="../Java/tutorial/on_java.html">Java</a>
| <a href="../php/phptut.html">PHP</a>
| <a href="../DesignPatterns/introduction.html">Design Patterns</a>
</div>
</div>

<div id="contenttext">

<!-- Use of this code assumes agreement with the Google Custom Search Terms of Service. -->
<!-- The terms of service are available at http://www.google.com/cse/docs/tos.html -->
<form name="cse" id="searchbox_demo" action="http://www.google.com/cse">
  <input type="hidden" name="cref" value="" />
  <input type="hidden" name="ie" value="utf-8" />
  <input type="hidden" name="hl" value="" />
  <input name="q" type="text" size="40" />
  <input type="submit" name="sa" value="Search" />
</form>
<script type="text/javascript" src="http://www.google.com/cse/tools/onthefly?form=searchbox_demo&lang="></script>

<div id="bookmarkshare">
<script type="text/javascript">var addthis_config = {"data_track_clickback":true};</script>
<a class="addthis_button" href="http://www.addthis.com/bookmark.php?v=250&amp;username=khhong7"><img src="http://s7.addthis.com/static/btn/v2/lg-share-en.gif" width="125" height="16" alt="Bookmark and Share" style="border:0"/></a><script type="text/javascript" src="http://s7.addthis.com/js/250/addthis_widget.js#username=khhong7"></script>
</div>

<br />
<div style="padding: 10px;"><span class="titletext">C++ Tutorial <br />
- Binary Tree Code Example</span></div>
<img src="../images/cplusplus/cpp_logo.jpg" alt="cplusplus logo"/>

<div class="bodytext" style="padding: 12px;" align="justify"> 
<div class="subtitle_2nd" id="FullList">Full List of C++ Tutorials</div>
<ul>
   <li><a href="cpptut.html">C++ Home</a> </li>
   <li><a href="string.html">String</a> </li>
   <li><a href="constructor.html">Constructor</a> </li>
   <li><a href="operatoroverloading.html">Operator Overloading</a> </li>
   <li><a href="virtualfunctions.html">Virtual Functions</a></li>
   <li><a href="dynamic_cast.html">Dynamic Cast Operator</a></li>
   <li><a href="typecast.html">Type Cast Operators</a></li>
   <li><a href="autoptr.html">Class auto_ptr</a></li>   
   <li><a href="templates.html">Templates</a></li>
   <li><a href="references.html">References for Built-in Types</a></li>
   <li><a href="valuevsreference.html">Pass by Value vs. Pass by Reference</a></li>
   <li><a href="memoryallocation.html">Memory Allocation</a></li>
   <li><a href="friendclass.html">Friend Functions and Friend Classes</a></li>
   <li><a href="functors.html">Functors (Function Objects)</a></li>
   <li><a href="statics.html">Static Variables and Static Class Members</a></li>
   <li><a href="exceptions.html">Exceptions</a></li>
   <li><a href="pointers.html">Pointers</a></li>
   <li><a href="pointers2.html">Pointers II</a></li>
   <li><a href="pointers3.html">Pointers III</a></li>
   <li><a href="smallprograms.html">Small Programs</a></li>
   <li><a href="linkedlist.html">Linked List Examples</a></li>
   <li><a href="binarytree.html">Binary Tree Example Code</a></li>
   <li><a href="stl.html">Standard Template Library (STL)</a></li>
   <li><a href="stl2.html">Standard Template Library (STL) II - Maps</a></li>
   <li><a href="stl3_iterators.html">Standard Template Library (STL) III - Iterators</a></li>
   <li><a href="slicing.html">Object Slicing and Virtual Table</a></li>
   <li><a href="this_pointer.html">The this Pointer</a></li>
   <li><a href="stackunwinding.html">Stack Unwinding</a></li>
   <li><a href="upcasting_downcasting.html">Upcasting and Downcasting</a></li>
   <li><a href="object_returning.html">Object Returning</a></li>
   <li><a href="private_inheritance.html">Private Inheritance</a></li>
   <li><a href="multithreaded.html">Multi-Threaded Programming - Terminology</a></li>
   <li><a href="multithreaded2.html">Multi-Threaded Programming II - C++ Thread for Win32</a></li>
   <li><a href="multithreaded3.html">Multi-Threaded Programming III - C++ Class Thread for Pthreads</a></li>
</ul>
</div>
<br />
<br />
<img src="images/binarytree/SoonChunMan.png" alt="SoonChunMan"/>
<br />
<br />


<div class="bodytext" style="padding: 12px;" align="justify">
<div class="subtitle" id="binarytreeexamples">Binary Tree Example Code</div>
<p>A <strong>binary tree</strong> is made of nodes, where each node contains a <strong>left</strong> pointer, a <strong>right</strong> pointer, and a <strong>data element</strong>. The <strong>root</strong> pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller <strong>subtrees</strong> on either side. A null pointer represents a binary tree with no elements -- the empty tree.</p>
<p>The formal recursive definition is: a <strong>binary tree</strong> is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a <strong>binary tree</strong>. </p>
<p>A <strong>binary search tree (BST)</strong> or <strong>ordered binary tree</strong> is a type of binary tree where the nodes are arranged in order: for each node, all elements in its left subtree are less-or-equal to the node (<=), and all the elements in its right subtree are greater than the node (&gt;). </p>
<p>Basically, binary search trees are fast at insert and lookup. On average, a binary search tree algorithm can locate a node in an N node tree in order <strong><i>log(n)</i></strong> time (log base 2). Therefore, binary search trees are good for <strong>dictionary</strong> problems where the code inserts and looks up information indexed by some key. The <strong><i>log(n)</i></strong> behavior is the average case -- it's possible for a particular tree to be much slower depending on its shape. 


<br /><br />
<img src="images/binarytree/binarytree_pic.png" alt="binarytree_pic"/>
<br />
<p>The following items are included in this Binary Tree code.</p>
<ul>
	<li>Look Up</li>
	<li>Size</li>
	<li>Maximum Depth</li>
	<li>Minimum Value</li>
      <li>In Order print</li>
	<li>Pre Order print</li>
	<li>Post Oder print</li>
</ul>
<br />
<br />
<pre>
/* Binary Tree */

#include &lt;iostream&gt;
using namespace std;

struct Node
{
	char data;
	Node *left;
	Node *right;
};

bool lookUp(struct Node *node, char target)
{
	if(node == NULL) return false;

	if(node->data == target) return true;
	else {
		if(node->data < target)
			return lookUp(node->right, target) ;
		else
			return lookUp(node->left, target);
	}
}

struct Node *newNode(int data) 
{
	Node *node = new Node;
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	return node;
}

struct Node* insertNode(struct Node *node, int data)
{
	if(node == NULL) return(newNode(data));
	if(data <= node->data ) 
		node->left = insertNode(node->left,data);
	else
		node->right = insertNode(node->right,data);
	return node;
}

int treeSize(struct Node *node)
{
	if(node == NULL) return 0;
	else
		return treeSize(node->left) + 1 + treeSize(node->right);
}

int maxDepth(struct Node *node)
{
	if(node == NULL) return 0;

	int leftDepth = maxDepth(node->left);
	int rightDepth = maxDepth(node->right);

	return leftDepth > rightDepth ? 
				leftDepth + 1 : rightDepth + 1;
}

char minValue(struct Node *node)
{
	Node *cur = node;
	while(cur->left) 
		cur = cur -> left;
	return cur->data;
}


void clear(struct Node *node)
{
	if(node != NULL) {
		clear(node->left);
		clear(node->right);
		delete node;
	}
}
/* print tree in order */
/* 1. Traverse the left subtree. 
   2. Visit the root. 
   3. Traverse the right subtree. 
*/
void printTreeInOrder(struct Node *node)
{
	if(node == NULL) return;

	printTreeInOrder(node->left);
	cout << node->data << " ";
	printTreeInOrder(node->right);
}

/* print tree in postorder*/
/* 1. Traverse the left subtree. 
   2. Traverse the right subtree. 
   3. Visit the root. 
*/
void printTreePostOrder(struct Node *node)
{
	if(node == NULL) return;

	printTreePostOrder(node->left);
	printTreePostOrder(node->right);
	cout << node->data << " ";
}

/* print in preorder */
/* 1. Visit the root. 
   2. Traverse the left subtree. 
   3. Traverse the right subtree. 
*/
void printTreePreOrder(struct Node *node)
{
	if(node == NULL) return;

	cout << node->data << " ";
	printTreePreOrder(node->left);
	printTreePreOrder(node->right);
}

int main(int argc, char **argv)
{
	Node *ptr;
	Node *root = newNode('F');
	insertNode(root,'B');
	insertNode(root,'A');
	insertNode(root,'D');
	insertNode(root,'C');  
	insertNode(root,'E');
	insertNode(root,'G');

	insertNode(root,'I');
	insertNode(root,'H');

	/* size of tree */
	cout << "size = " << treeSize(root) << endl;

	/* max depth */
	cout << "max depth = " << maxDepth(root) << endl;

	/* min value */
	if(root) 
		cout << "min value = " << minValue(root) << endl;

	/* print tree in order */
	cout << "increasing sort order\n";
	printTreeInOrder(root);
	cout << endl;

	/* print tree in postorder*/
	cout << "post order \n";
	printTreePostOrder(root);
	cout << endl;

	/* print tree in preorder*/
	cout << "pre order \n";
	printTreePreOrder(root);
	cout << endl;

	/* deleting a tree */
	clear(root);
}
</pre>
<p>From the run, we get:</p>
<img src="images/binarytree/binarytree_output.png" alt="binarytree_output"/>

<div id="rightpanel">
<div align="center">
</div></div>

<br /><br />
<div class="subtitle_2nd" id="FullList">Full List of C++ Tutorials</div>
<ul>
   <li><a href="cpptut.html">C++ Home</a> </li>
   <li><a href="string.html">String</a> </li>
   <li><a href="constructor.html">Constructor</a> </li>
   <li><a href="operatoroverloading.html">Operator Overloading</a> </li>
   <li><a href="virtualfunctions.html">Virtual Functions</a></li>
   <li><a href="dynamic_cast.html">Dynamic Cast Operator</a></li>
   <li><a href="typecast.html">Type Cast Operators</a></li>
   <li><a href="autoptr.html">Class auto_ptr</a></li>
   <li><a href="templates.html">Templates</a></li>
   <li><a href="references.html">References for Built-in Types</a></li>
   <li><a href="valuevsreference.html">Pass by Value vs. Pass by Reference</a></li>
   <li><a href="memoryallocation.html">Memory Allocation</a></li>
   <li><a href="friendclass.html">Friend Functions and Friend Classes</a></li>
   <li><a href="functors.html">Functors</a></li>
   <li><a href="statics.html">Static Variables and Static Class Members</a></li>
   <li><a href="exceptions.html">Exceptions</a></li>
   <li><a href="pointers.html">Pointers</a></li>
   <li><a href="pointers2.html">Pointers II</a></li>
   <li><a href="pointers3.html">Pointers III</a></li>
   <li><a href="smallprograms.html">Small Programs</a></li>
   <li><a href="linkedlist.html">Linked List Examples</a></li>
   <li><a href="binarytree.html">Binary Tree Example Code</a></li>
   <li><a href="stl.html">Standard Template Library (STL)</a></li>
   <li><a href="stl2.html">Standard Template Library (STL) II - Maps</a></li>
   <li><a href="stl3_iterators.html">Standard Template Library (STL) III - Iterators</a></li>
   <li><a href="slicing.html">Object Slicing and Virtual Table</a></li>
   <li><a href="this_pointer.html">The this Pointer</a></li>
   <li><a href="stackunwinding.html">Stack Unwinding</a></li>
   <li><a href="upcasting_downcasting.html">Upcasting and Downcasting</a></li>
   <li><a href="object_returning.html">Object Returning</a></li>
   <li><a href="private_inheritance.html">Private Inheritance</a></li>
   <li><a href="multithreaded.html">Multi-Threaded Programming - Terminology</a></li>
   <li><a href="multithreaded2.html">Multi-Threaded Programming II - C++ Thread for Win32</a></li>
   <li><a href="multithreaded3.html">Multi-Threaded Programming III - C++ Class Thread for Pthreads</a></li>
</ul>
<br /><br />



<script type="text/javascript"><!--
google_ad_client = "pub-5767010733052716";
/* 300x250, created 7/22/10 */
google_ad_slot = "4543448457";
google_ad_width = 300;
google_ad_height = 250;
//-->
</script>
<script type="text/javascript"
src="http://pagead2.googlesyndication.com/pagead/show_ads.js">
</script>
<br />


<br />
<br />
<br />


</div>
</div>
<div class="smallgraytext" id="footer"><a href="../index.html">Home</a>
| <a href="../about_us.html">About Us</a>
| <a href="../products.html">products</a>
| <a href="../our_services.html">Our Services</a>
| <a href="#">Contact Us</a>
| Bogotobogo &copy; 2010 | <a target="_blank" href="http://www.bogotobogo.com">Bogotobogo </a>
</div>
</div>
</div>
</body>
</html>
